#include "linklist.h"

// 创建单链表, 为头节点在堆区分配内存空间
linknode *create_empty_linklist() {
    linknode *head = NULL;
    head = (linknode *) malloc(sizeof(linknode));
    if (NULL == head) {
        printf("malloc failed\n");
        return NULL;
    }
    memset(head, 0, sizeof(linknode));

    // head->data = 0;
    // head->next = NULL;
    return head;
}

//头插法 插入数据 插入顺序和输出顺序是反的
void insert_head_linklist(linknode *head, datatype data) {
    // 先为节点在堆区申请空间
    linknode *temp = (linknode *) malloc(sizeof(linknode));
    if (NULL == temp) {
        printf("malloc failed\n");
    }
    temp->data = data;
    temp->next = head->next;
    head->next = temp;

}
//输出
void print_data_linklist(linknode *head) {
    linknode *p = head->next;
    while(NULL != p) {
        printf("%d \n", p->data);
        p = p->next;
    }
}

// 链表判空
int is_empty_linklist(linknode * head) {
    return head->next == NULL ? 1 : 0;
}

// 删除链表中的一个元素
int delete_data(linknode * head, datatype x) {
    if (is_empty_linklist(head)) return -1;
   linknode * p = head;
   linknode *q = NULL;
   int flag = 0;
   while(NULL != p->next) {
        if (p->next->data == x) {
            //删除该节点
            q = p->next;
            p->next = q->next;
            free(q);
            q = NULL;
            flag = 1;
        } else {
            p = p->next;
        }
   }
   if (flag == 0) {
    printf("没有找到该元素\n");
   } else {
    printf("删除成功\n");
   }
   return 1;

}

// 实现链表逆置
void reverse_linklist(linknode * head)
{

    // 1. 第一个有效数据节点的指针域置为NULL
    //2. 从第二个节点开始，向后遍历依次向头节点插入
    // head 1 2(p) 3(q)

    linknode * p = head->next->next;
    // 先置p的位置为空
    head->next->next = NULL;
    linknode *q = NULL;
    while(p != NULL) {
        q = p->next;
        p->next = head->next;
        head->next = p;
        p = q;
    }
         
}
// 清空链表中的元素
void clear_linklist(linknode * head) {
    linknode *p = head;
    linknode *q = NULL;

    while(p != NULL) {
        q = p->next;
        free(p);
        p = q;
    }
    return ;
}
